Vehicle route problem with mixed integer programming by Himanshu Bhardwaj
Problem
There are n customers locations and a depot location. At the customer's locations, there is some delivery and pickup demands. A depot has m vehicles and all the vehicles have capacity C. Rij is the amount of the delivery amount on borad between the nodes i and j and Pij is the pickup amount on board between the nodes i and j. cost for each of the vehicles is $1000 per km. With help of this model following Questions can be answered.
(1) What is the optimum number of vehicles to be used.
(2) What are the optimum route map for each vehicles.
(3) What should be the delivery amount for each vehicles at each of the customer nodes the vehicles visit.
(4) Pick up amount of each vehicles at each nodes the vehicles visit.
cost function
$\sum\limits_{i=0}^n \sum\limits_{j=0}^n d_{ij} x_{ij}$
Constraints
$\sum\limits_{i=0}^n x_{ij} = 1, where, j \in \{1,....n\}$
$\sum\limits_{j=0}^n x_{ji} = 1, where, i \in \{1,....n\} $
$\sum\limits_{i=0}^n R_{ij} - q_{j} = \sum\limits_{i=0}^n R_{ji}, where, j \in \{1,2,...,n\} $
$\sum\limits_{i=0}^n P_{ij} + b_{j} = \sum\limits_{i=0}^n P_{ji}, where, j \in \{1,2,...,n\} $
$\sum\limits_{i=0}^n R_{i0} = 0 $
$\sum\limits_{i=0}^n P_{0i} = 0 $
$R_{ij} + P_{ij} = Cx_{ij} $
$R_{ij} >= 0, P_{ij} >=0 $
$x_{0j} <= number of vehicles $
where,
dij : cost of travel from i to j
qi : delivery demand at node i
bi: pickup demand at node i
C : vehicle capacity
Rij: amount of delivery goods on board between nodes i and j
Pij: amount of pick up goods on board between nodes i and j
import pandas as pd
import numpy as np
import matplotlib.pyplot as plt
import gurobipy as g
from gurobipy import GRB
import osmnx as ox
import plotly.graph_objects as pt
import networkx as nx
import pulp
import random
graph = ox.load_graphml('Brooklyn_subset.graphml')
ox.plot_graph(graph, figsize=(12,12))
points = pd.read_csv('del_points.csv')
points.head()
c = np.random.randint(0,27,12)
customers = points.loc[c]
lat = []
lon = []
for i in range(len(customers)):
lat.append(customers.iloc[i,1])
lon.append(customers.iloc[i,2])
latm = np.mean(lat)
lonm = np.mean(lon)
Location of the customers
fig = pt.Figure(pt.Scattermapbox(name='Customers', mode='markers',lat=lat, lon=lon, marker={'size': 10, 'color': 'purple'}))
#fig.add_trace(pt.Scattermapbox(name='center', mode='markers', lat=[latm], lon=[lonm], marker={'size':13, 'color':'red'}))
fig.update_layout(mapbox_style = 'stamen-terrain', mapbox_center_lat = latm, mapbox_center_lon = lonm)
fig.update_layout(margin = {'r':0, 'l':0, 'b':0, 't':0}, mapbox={'center':{'lat':latm, 'lon':lonm}, 'zoom':13})
fig.show()
def get_distance(G, p1, p2):
n1 = ox.get_nearest_node(G,[p1[0],p1[1]])
n2 = ox.get_nearest_node(G,[p2[0],p2[1]])
d = nx.shortest_path_length(G, n1, n2, weight='length')
return d
customers = customers.reset_index()
customers = customers.drop(['index', 'FID'], axis=1)
customers
import vehicle_model as vm
#calculation of cost matrix
cm = [[vm.get_distance(graph, list(customers.loc[i]), list(customers.loc[j]))
for i in range(len(customers))] for j in range(len(customers))]
pd.DataFrame(cm)
generating random delivery and pickup demand at the customer location
demand = np.random.randint(1000,2000,12)
demand[0] = 0
demand
pickup = np.random.randint(800,1500, 12)
pickup
capacityofvehicles = 6000
numberofvehicles = 4
m = vm.solve(cm, demand, pickup,capacityofvehicles, numberofvehicles)
print(m.ObjVal)
for v in m.getVars():
print(v.varname,"=",v.x)
pt = vm.get_path(m)
routes = vm.get_GISpath(graph, pt, customers)
route map of all the vehicles
vm.plot_all_route(graph, customers, routes)
route map of vehicle 1
vm.plot_single_route(graph, customers, routes[1])
route map of vehicle 2
vm.plot_single_route(graph, customers, routes[2])
route map of vehicle 3
vm.plot_single_route(graph, customers, routes[3])
route map of vehicle 4
#vm.plot_single_route(graph, customers, routes[4])
vR = {}
for v in m.getVars():
if(v.x > 1):
# print(v.name, " = ", v.varValue)
temp = (v.varName.split('|')[1]).split(',')
#print(temp[0],",", temp[1])
vR[v.varName] = round(v.x,2)
#print(v.varName, "=", v.x)
Pick up and deliver amount for each vehicle here r represents delivery amount, z represents pickup amount.
vR